package com.kk.datastructure.search;

import java.util.ArrayList;
import java.util.List;

/**
 * title: 二分查找（单，多数版）
 * @author 阿K
 * 2020年12月22日 下午9:56:17 
 */
public class BinarySearch {

	public static void main(String[] args) {
		int arr[] = { 1, 8, 10, 89, 1000, 1000, 1234 };

		int findVal = 1000;
		System.out.println(binarySearch(arr, 0, arr.length - 1, findVal));
		System.out.println(binarySearchS(arr, 0, arr.length - 1, findVal));
	}

	/**
	 * 二分查找(单数版)
	 * 
	 * @param arr     原始数组
	 * @param left    左边索引
	 * @param right   右边索引
	 * @param findVal 查找的值
	 * @return
	 */
	public static int binarySearch(int[] arr, int left, int right, int findVal) {

		// 当 left > right 时候，说明已经递归完毕，仍没有找到
		if (left > right) {
			return -1;
		}

		// 折半，取值
		int mid = (left + right) / 2;
		int midVal = arr[mid];

		if (findVal > midVal) {// 向右递归
			return binarySearch(arr, mid + 1, right, findVal);
		} else if (findVal < midVal) {// 向左递归
			return binarySearch(arr, left, mid - 1, findVal);
		} else {
			return mid;
		}
	}

	/**
	 * 二分查找(多数版)
	 * 
	 * @param arr     原始数组
	 * @param left    左边索引
	 * @param right   右边索引
	 * @param findVal 查找的值
	 * @return
	 */
	public static List<Integer> binarySearchS(int[] arr, int left, int right, int findVal) {

		// 当 left > right 时，说明已经递归完毕，仍没有找到
		if (left > right) {
			return new ArrayList<Integer>();
		}

		// 折半取值
		int mid = (left + right) / 2;
		int midVal = arr[mid];

		if (findVal > midVal) {
			// 右递归
			return binarySearchS(arr, mid + 1, right, findVal);
		} else if (findVal < midVal) {
			// 左递归
			return binarySearchS(arr, left, mid - 1, findVal);
		} else {
			// ****************以下代码才是和简单版的区别所在，以上都一样*******
			// 1、找到第一个匹配的索引值 mid 的时候，不要马上返回
			// 用于接受结果
			List<Integer> resIndexList = new ArrayList();

			// 2、向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回
			int temp = mid - 1;// 左递归起始索引
			while (true) {
				if (temp < 0 || arr[temp] != findVal) {
					break;// 不满足，退出(固二分为有序，左边的第一个不相同，再找也是不同)
				} else {
					// 加入，左移（再找）
					resIndexList.add(temp);
					temp -= 1;
				}
			}
			resIndexList.add(mid);

			// 3、向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回
			temp = mid + 1;
			while (true) {
				if (temp > arr.length - 1 || arr[temp] != findVal) {
					break;
				} else {
					resIndexList.add(temp);
					temp += 1;
				}
			}
			return resIndexList;
		}
	}
}
